package main

import "fmt"

/*
最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"
*/

//中心扩散法
//枚举每个奇偶长度的回文串的中心起点，找最长的可能性
func longestPalindrome1(s string) (res string) {
	for i, n := 0, len(s); i < n; i++ {
		l, r := i, i
		for l >= 0 && r < n && s[l] == s[r] {
			l--
			r++
		}

		if r-l-1 > len(res) {
			res = s[l+1 : r]
		}
		l, r = i, i+1
		for l >= 0 && r < n && s[l] == s[r] {
			l--
			r++
		}
		if r-l-1 > len(res) {
			res = s[l+1 : r]
		}
	}
	return
}

func longestPalindrome2(s string) (res string) {
	cur := ""
	for i := 0; i < len(s); i++ {
		//以s[i]为中心寻找最长子串
		s1 := palindrome(s, i, i)
		//以s[i+1]为中心寻找最长子串
		s2 := palindrome(s, i, i+1)
		cur = lenMax(s1, s2)
		res = lenMax(res, cur)
	}
	return res
}

//寻找回文子串
func palindrome(s string, l, r int) string {
	for l >= 0 && r < len(s) && s[l] == s[r] {
		//向两边扩散
		l--
		r++
	}
	return s[l+1 : r]
}

func lenMax(a, b string) string {
	if len(a) > len(b) {
		return a
	}
	return b
}

func main() {
	fmt.Println(longestPalindrome2("abdasffdaskjhfasdjhfjkdstyyyt"))
}
